package problem124;

//124.二叉树中的最大路径和
//https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
    int ret = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxPath(root);
        return ret;
    }
    public int maxPath(TreeNode root) {
        if(root == null) return 0;
        int max = root.val;

        int lmax = maxPath(root.left);
        int rmax = maxPath(root.right);

        if(lmax < 0 && rmax < 0) max = root.val;
        else max = root.val + Math.max(lmax, rmax);

        //四种方案里取最大值
        int a = root.val + lmax;
        int b = root.val + rmax;
        int c = root.val + lmax + rmax;
        int d = root.val;
        ret = Math.max(Math.max(ret, a), Math.max(b, c));
        ret = Math.max(ret, d);
        
        return max;
    }
}